package link_list


/*
	力扣原题：LCR 027. 回文链表
	链接：   https://leetcode.cn/problems/aMhZSa/
*/

type ListNode struct {
	Val  int
	Next *ListNode
}

func isPalindrome(head *ListNode) bool {
	if head == nil {
		return true
	}
	// 找到前中点
	slow, fast :=  head, head
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	preMid := slow
	// 对中点后续的节点反转链表
	var pre, next *ListNode = nil, preMid
	for next != nil {
		tem := next.Next
		next.Next = pre
		pre = next
		next = tem
	}
	// 校验是否是回文链表
	p1, p2 := head, pre
	ans := true
	for p1 != nil && p2 != nil {
		if p1.Val != p2.Val {
			ans = false
			break
		}
		p1 = p1.Next
		p2 = p2.Next
	}
	// 还原链表
	pre, next = nil, pre
	for next != nil {
		tem := next.Next
		next.Next = pre
		pre = next
		next = tem
	}
	return ans
}
